Bubble Sort


Bubble Sort
Bubble Sort
 
[dt. »blasenartiges Sortieren«], ein einfacher Algorithmus für die Sortierung von Daten. Das Verfahren beruht darauf, dass die Elemente des Bestands mehrfach nacheinander durchgesehen werden, bei jedem Durchgang wird das größte bzw. kleinste Element entfernt und an die (sortierte) Ergebnisliste angehängt. Bei einem Durchgang werden jeweils zwei benachbarte Elemente verglichen und vertauscht, wenn sie nicht in der korrekten Reihenfolge stehen. Im Ergebnis eines Durchgangs steht das größte (kleinste) Element am Ende und kann entfernt werden. Wenn der unsortierte Rest nur noch aus einem Element besteht, ist die Sortierung beendet.
 
Stellt man den (unsortierten) Datenbestand in einer senkrechten Reihe dar, dann kann man das Verfahren mit dem Aufsteigen von Blasen (engl. bubbles) in einem Sprudelglas vergleichen: Große »Blasen« (d. h. zu sortierende Daten) steigen solange auf, bis sie durch eine noch größere Blase aufgehalten werden, die ihrerseits weiter aufsteigt.
 
Das Bubble-Sort-Verfahren eignet sich nur für kleine Datenbestände (max. 50 Elemente), da die Laufzeit quadratisch mit der Zahl der Elemente steigt. Schnellere Sortierverfahren sind z. B. Heap Sort oder Quick Sort.

Universal-Lexikon. 2012.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • bubble sort — noun (computing) A method of sorting items of data in a list by repeatedly scanning the list and putting adjacent pairs of items in order • • • Main Entry: ↑bubble …   Useful english dictionary

  • Bubble sort — Infobox Algorithm class=Sorting algorithm data=Array time= О(n²) space= О(n) total, O(1) auxiliary optimal=NoBubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time… …   Wikipedia

  • Bubble-Sort — Das Sortieren durch Aufsteigen (englisch Bubble sort, Blasensortierung ) bezeichnet einen einfachen, stabilen Sortieralgorithmus, der eine Reihe zufällig angeordneter Elemente (etwa Zahlen) der Größe nach ordnet. Bubblesort wird von Donald E.… …   Deutsch Wikipedia

  • Bubble Sort — Das Sortieren durch Aufsteigen (englisch Bubble sort, Blasensortierung ) bezeichnet einen einfachen, stabilen Sortieralgorithmus, der eine Reihe zufällig angeordneter Elemente (etwa Zahlen) der Größe nach ordnet. Bubblesort wird von Donald E.… …   Deutsch Wikipedia

  • bubble sort — rikiavimas burbulo metodu statusas T sritis informatika apibrėžtis ↑Rikiavimo metodas, kai palyginami du gretimi sąrašo elementai ir, jeigu jie sudėti ne pagal ↑rikiavimo eilę, sukeičiami vietomis. Kartojant operaciją paeiliui su visais… …   Enciklopedinis kompiuterijos žodynas

  • Bubble Sort — Tri à bulles Exemple du tri à bulles utilisant une liste de nombres aléatoires Le tri à bulles ou tri par propagation est un algorithme de tri qui consiste à faire remonter progressivement les plus petits éléments d une liste, comme les bulles d… …   Wikipédia en Français

  • bubble sort — noun A sorting algorithm in which neighboring two values are compared and swapped into right order if necessary in the most inner loop …   Wiktionary

  • bubble sort — system of classification …   English contemporary dictionary

  • Bubble Bobble — Éditeur Taito Développeur Taito Concepteur Fukio Mitsuji …   Wikipédia en Français

  • Bubble Bobble also featuring Rainbow Islands — Bubble Bobble Bubble Bobble Éditeur Taito Développeur Taito Concepteur Fukio Mitsuji …   Wikipédia en Français